package recursion.迷宫问题;

/**
 * 一个迷宫，抽取出8*7的二维数组，墙壁和挡板填充为 1 ;
 * 没有优化 ， 全靠小球策略
 */
public class 迷宫问题 {
    public static void main(String[] args) {
       goMap(miGong(),1,1);

    }
    // 构建一个迷宫地形
    public static int[][] miGong(){
        int [][]map = new int[8][7];
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i <8 ; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        // 设置挡板
        map[3][1] = 1;
        map[3][2] = 1;
        return map;

    }

    /**
     *
     * @param map 传递一个地图
     * @param i   从那个位置开始
     * @param j   从那个位置开始
     * @return 找到路返回真
     * 当map[i][j] 为1，墙；为2；走过当路；为3表示该点走不通
     * 在走迷宫时，需要确定一个策略，下-右-上-左
     */
    public static boolean goMap(int [][] map,int i,int j){
        System.out.println("迷宫情况为");
        for (int[] row : map){
            for (int data:row){
                System.out.printf("%3d\t",data);
            }
            System.out.println();
        }
        // 通路已经找到
        if(map[6][1] == 2){
            return true;
        }
        if (map[i][j]==0){
            map[i][j]=2;
            if (goMap(map,i+1,j)){
                return true;
            }else if(goMap(map,i,j+1)){
                return true;
            }else if(goMap(map,i-1,j)){
                return true;
            }else if(goMap(map,i,j-1)) {
                return true;
            }else {
                map[i][j] = 3; // 该点走不通是思路
                return  false;
            }

        }
        // map[i][j] 可能是1、2、3
        return false;
    }

}
